package nowCoder;

import java.util.Stack;

/**
 * Created by Ghost on 2015/1/26 0026.
 */
class TreeNode {
    TreeNode(String data){
        this.data = data;
    }
    TreeNode left, right;   //左右子树
    String data;         //数据
}

public class MirrorTreeWithoutRecurrence {
    private Stack<TreeNode> stack = new Stack<TreeNode>();

    private void reverse(TreeNode ele) {
        if(ele!=null){
            TreeNode l = ele.left;
            ele.left = ele.right;
            ele.right = l;
        }

    }

    public void mirror(TreeNode root) {
        TreeNode tmp = root;
        while(!stack.isEmpty() || tmp!=null){//pay attention on the loop condition
            while (tmp != null) {
                stack.push(tmp);
                tmp = tmp.left;
            }

            TreeNode t = stack.pop(); //think clear about this function
            tmp = t.right;
            reverse(t);
        }
    }

    public static void main(String[] args){
        MirrorTreeWithoutRecurrence mirrorTreeWithoutRecurrence = new MirrorTreeWithoutRecurrence();
        TreeNode treeNode = new TreeNode("1");
        treeNode.left = new TreeNode("2");
        treeNode.right = new TreeNode("3");
        treeNode.left.left = new TreeNode("4");
        treeNode.left.right = new TreeNode("5");
        treeNode.right.left = new TreeNode("6");
        treeNode.right.right = new TreeNode("7");
        treeNode.left.left.left = new TreeNode("8");
        treeNode.left.left.left.left =  new TreeNode("9");
        treeNode.left.left.left.right =  new TreeNode("10");

        mirrorTreeWithoutRecurrence.mirror(treeNode);
    }
}
